A matching processing of a signal, particularly, a matching processing of an image signal has a problem of generally causing a large amount of calculation. A motion vector detection by block matching as described below is an example of using the matching processing.
Namely, in an image signal processing apparatus, motion detection for obtaining a motion vector indicating a motion of an image is one major technique for effectively performing the motion image compression. There are some proposed methods of obtaining the motion vector, but one major method is a method called block a matching algorithm.
FIG. 1 is a block diagram showing an example of a configuration of a motion detection device in an image signal processing apparatus of the related art, wherein the block matching algorithm is applied.
The motion detection device 1 comprises frame memories 2 and 3 and a motion vector detection portion 4.
In the motion detection device 1, when an image signal is input from an input terminal TIN, an information of one frame is stored in the frame memory 2.
When an information of the next image is input, the previous (previously input) information in the frame memory 2 is stored in the frame memory 3, and the currently (this time) input information is stored in the frame memory 2.
Namely, an information of a current frame Fc is stored in the frame memory 2, and an information of a reference frame Fr is stored in the frame memory 3.
Next, the information of the current frame Fc and the reference frame Fr is sent to the vector detection portion 4 and divided to blocks in the motion vector detection portion 4 where a motion vector (Vx, Vy) is detected and output from a terminal TOUT.
FIG. 2 is a view for explaining an outline of block matching algorithm. Below, the outline of algorithm will be explained with reference to FIG. 2.
In this algorithm, a motion vector of a focused pixel Fc (x, y) in the current frame Fc is obtained by calculating a differential absolute value sum of corresponding pixels in pixels in a reference block range (L×L) having the focused pixel Fc (x, y) at its center and pixels in the same block range as the above block range (L×L) in a search area SR in the reference frame Fr.
The above calculation is repeated while moving the block range extracted in the search area SR by one pixel, and a differential vector of the center position of a block having the smallest differential absolute value sum in all blocks and the focused pixel position is regarded as the solution (motion vector).
Next, a processing procedure of detecting a motion vector of the pixel Fc (x, y) in the current frame Fc will be explained in detail with reference to FIG. 3.
Step ST1:
In the step ST1, a search area SR using as a reference the same position in the reference frame as the position (x, y) of the focused pixel is determined after starting processing ST0.
Step ST2:
In the step ST2, the maximum value of a calculation formula is substituted to initialize a variable “min” storing the minimum value of a calculation result. When assuming that one pixel is 8 bits and the number of pixels in a block is 16, 28×16=4096 is assigned to the variable “min”.
Step ST3:
In the step ST3, a counter variable “n” for counting blocks in a search area SR is initialized to be “1”
Step ST4:
In the step ST4, a variable “sum” for being substituted a calculation result is initialized to be “0”.
Step ST5:
In the step ST5, assuming that a range of a reference block is L×L, a pixel in a certain block in the current frame is Fc (i, j), and a pixel in the k-th block in the search area SR of the reference frame Fr is Frk (i, j), calculation of a differential absolute value sum of corresponding pixels, that is, the formula 1 below is performed and the calculation result is substituted for “sum”.
                                          ∑                          i              =              1                        L                    ⁢                      ∑                          j              =              1                        L                          =                                                      Fc              ⁡                              (                                  i                  ,                  j                                )                                      -                          Frk              ⁡                              (                                  i                  ,                  j                                )                                                                                  (        1        )            
Step ST6
In the step ST6, the relationship of large and small is distinguished between the calculated differential absolute value sum “sum” and the minimum value “min” of the differential absolute value sum. When the calculated differential absolute value sum “sum” is smaller, the procedure proceeds to a step ST7, while when it is larger (including being equal), the calculation result is not the minimum value, so that the step ST7 is skipped and the procedure proceeds to a step ST8.
Step ST7:
In the step ST7, the calculation result “sum” is updated by the minimum value “min”, and a counter value “n” of the block as a motion vector number is set.
Step ST8:
In the step ST8, if the block counter value “n” is the total number of blocks in the search area SR, that is, the final block comes, it means the finish, so the procedure proceeds to a step ST10, while if it is not the final block, the procedure proceeds to a step ST9.
Step ST9:
In the step ST9, the block counter value “n” is incremented to “n+1”, and the procedure proceeds to the step ST4 to repeat the calculation.
Step ST10:
In the step ST10, a motion vector is obtained from the center pixel and (x, y) of a block having a number stored in a motion number and output the same.
Since the block matching algorithm explained above repeats the calculation of the formula (1), there is a disadvantage that an amount of the calculation becomes enormous and most of the time of image compression processing, such as MPEG, is spent for that.